package problem47_PermutationsII;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
	private final List<List<Integer>> result = new LinkedList<>();

	public List<List<Integer>> permuteUnique(int[] nums) {
		Integer[] nums2 = new Integer[nums.length];
		for (int i = 0; i < nums.length; i++)
			nums2[i] = nums[i];
		dfs(nums2, 0, nums2.length);
		return result;
	}

	private void dfs(Integer[] nums, int start, int end) {
		if (start == end)
			result.add(new LinkedList<>(Arrays.asList(nums)));
		for (int i = start; i < end; i++) {
			if(existBefore(nums,start,i)) continue;
			swap(start, i, nums);
			dfs(nums, start + 1, end);
			swap(start, i, nums);
		}

	}

	private boolean existBefore(Integer[] array, int begin, int i) {
		for (int j = begin; j < i; j++) {
			if (array[j] == array[i])
				return true;
		}
		return false;
	}

	private void swap(int i, int j, Integer[] nums) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
	
	public static void main(String[] args){
		System.out.println(new Solution().permuteUnique(new int[]{3,1,1,3}));
	}
}
